/*********************************************************************************************************
 *  ------------------------------------------------------------------------------------------------------
 *  file description
 *  ------------------------------------------------------------------------------------------------------
 *         \file  set.c
 *        \brief  This is a general-purpose C language set module, with common data structure
 *       \author  Lamdonn
 *        \email  Lamdonn@163.com
 *      \version  1.1.0
 *      \license  GPL2
 *    \copyright  Copyright (C) 2023 Lamdonn.
 ********************************************************************************************************/
#include "vlib.h"
#include <stdlib.h>
#include <string.h>

#define IDENT                           (6)

/* set node type define */
typedef struct NODE
{
    struct NODE *parent;                /* parent node */
    struct NODE *left;                  /* left node */
    struct NODE *right;                 /* right node */
    int color;                          /* red black color */
    int index;                          /* node index */
    void *data;                         /* address of data */
} NODE, *node_t;

/* set node color */
#define SET_COLOR_BLACK                 (0)
#define SET_COLOR_RED                   (1)

/* set child */
#define SET_CHILD_LEFT                  (0)
#define SET_CHILD_RIGHT                 (1)

set_t set_create(int dsize)
{
    set_t set = NULL;

    if (dsize <= 0) return NULL;

    /* alloc set space */
    set = (set_t)vlib_malloc(sizeof(SET));
    if (set == NULL) return NULL;

    /* alloc nil node space */
    set->nil = vlib_malloc(sizeof(NODE));
    if (set->nil == NULL)
    {
        vlib_free(set);
        return NULL;
    }

    /* alloc nil data space */
    ((node_t)(set->nil))->data = vlib_malloc(dsize);
    if (((node_t)(set->nil))->data == NULL)
    {
        vlib_free(set->nil);
        vlib_free(set);
        return NULL;
    }

    ((node_t)(set->nil))->color = SET_COLOR_BLACK;
    set->parent.ident = IDENT;
    set->parent.base = set->nil;
    set->parent.size = 0;
    set->parent.dsize = dsize;

    return set;
}

/** recursion_delete_node
 *  \brief recursively delete all nodes under the node
 *  \param[in] set: set handler
 *  \param[in] node: set node
 *  \return none
 */
static void recursion_delete_node(set_t set, node_t node)
{
    if (node == set->nil) return;

    /* recursive call */
    recursion_delete_node(set, node->left);
    recursion_delete_node(set, node->right);

    /* release */
    vlib_free(node->data);
    vlib_free(node);
}

void set_delete(set_t set)
{
    if (!set) return;

    set_clear(set);
    vlib_free(((node_t)(set->nil))->data);
    vlib_free(set->nil);
    vlib_free(set);
}

/** set_find_node
 *  \brief find node by index
 *  \param[in] set: set handler
 *  \param[in] index: index
 *  \return node or nil: fail
 */
static node_t set_find_node(set_t set, int index)
{
    node_t node = set->parent.base;

    /* binary search */
    while (node != set->nil)
    {
        if (index < node->index)
        {
            node = node->left;
        }
        else if (index > node->index)
        {
            node = node->right;
        }
        else
        {
            return node;
        }    
    }

    return set->nil;
}

/** set_left_rotate
 *  \brief tree left rotation
 *  \param[in] set: set handler
 *  \param[in] x: node to be rotated
 *  \return none
 */
static void set_left_rotate(set_t set, node_t x) 
{
    node_t y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> right

    x->right = y->left; // 1 1
    if (y->left != set->nil) // 1 2
    {
        y->left->parent = x;
    }

    y->parent = x->parent; // 1 3
    if (x->parent == set->nil) // 1 4
    {
        set->parent.base = y;
    }
    else if (x == x->parent->left)
    {
        x->parent->left = y;
    }
    else
    {
        x->parent->right = y;
    }

    y->left = x; //1 5
    x->parent = y; //1 6
}

/** set_right_rotate
 *  \brief tree right rotation
 *  \param[in] set: set handler
 *  \param[in] x: node to be rotated
 *  \return none
 */
static void set_right_rotate(set_t set, node_t y) 
{
    node_t x = y->left;

    y->left = x->right;
    if (x->right != set->nil)
    {
        x->right->parent = y;
    }

    x->parent = y->parent;
    if (y->parent == set->nil)
    {
        set->parent.base = x;
    }
    else if (y == y->parent->right)
    {
        y->parent->right = x;
    }
    else
    {
        y->parent->left = x;
    }

    x->right = y;
    y->parent = x;
}

/** set_insert_fixup
 *  \brief maintaining the properties of red-black tree after inserting node
 *  \param[in] set: set handler
 *  \param[in] z: node to be insert
 *  \return none
 */
static void set_insert_fixup(set_t set, node_t z) 
{
    node_t y = NULL;

    while (z->parent->color == SET_COLOR_RED) // z ---> SET_COLOR_RED
    {
        if (z->parent == z->parent->parent->left)
        {
            y = z->parent->parent->right;

            /* the uncle node of the inserted node is red */
            if (y->color == SET_COLOR_RED)
            {
                z->parent->color = SET_COLOR_BLACK;
                y->color = SET_COLOR_BLACK;
                z->parent->parent->color = SET_COLOR_RED;

                z = z->parent->parent; //z --> SET_COLOR_RED
            }
            else
            {
                /* the uncle node is black, and the inserted node is the right child of the parent node */
                if (z == z->parent->right)
                {
                    z = z->parent;
                    set_left_rotate(set, z);
                }

                z->parent->color = SET_COLOR_BLACK;
                z->parent->parent->color = SET_COLOR_RED;
                set_right_rotate(set, z->parent->parent);
            }
        }
        else
        {
            /* the uncle node of the inserted node is red */
            y = z->parent->parent->left;
            if (y->color == SET_COLOR_RED)
            {
                z->parent->color = SET_COLOR_BLACK;
                y->color = SET_COLOR_BLACK;
                z->parent->parent->color = SET_COLOR_RED;

                z = z->parent->parent; //z --> SET_COLOR_RED
            }
            else
            {
                /* the uncle node is black, and the inserted node is the left child of the parent node */
                if (z == z->parent->left)
                {
                    z = z->parent;
                    set_right_rotate(set, z);
                }
        
                z->parent->color = SET_COLOR_BLACK;
                z->parent->parent->color = SET_COLOR_RED;
                set_left_rotate(set, z->parent->parent);
            }
        }
    }

    ((node_t)(set->parent.base))->color = SET_COLOR_BLACK;
}

/** set_insert_node
 *  \brief insert node into set
 *  \param[in] set: set handler
 *  \param[in] z: node to be insert
 *  \return none
 */
static void set_insert_node(set_t set, node_t z)
{
    /* use fast and slow pointers to traverse the red black set. the slow pointer is the father of the fast pointer */
    node_t y = set->nil;
    node_t x = set->parent.base;

    while (x != set->nil)
    {
        y = x;
        if (z->index < x->index)
        {
            x = x->left;
        }
        else if (z->index > x->index)
        {
            x = x->right;
        }
        else /* A node with index z ->index already exists, and it returns directly */
        {
            return;
        }
    }

    z->parent = y;
    /* the original set is empty, and the newly inserted node is the root node */
    if (y == set->nil)
    {
        set->parent.base = z;
    }
    else if (z->index < y->index)
    {
        y->left = z;
    }
    else
    {
        y->right = z;
    }

    z->left = set->nil;
    z->right = set->nil;
    z->color = SET_COLOR_RED; /* the newly inserted node is red by default */

    /* maintain the properties of set */
    set_insert_fixup(set, z);
}

int set_insert(set_t set, int index, void* data)
{
    node_t parent_node = NULL;
    node_t new_node = NULL;
    int child = 0;

    if (!set) return 0;
    
    /* alloc new node */
    new_node = (node_t)vlib_malloc(sizeof(NODE));
    if (new_node == NULL)
    {
        return 0;
    }

    /* alloc data space */
    new_node->data = vlib_malloc(set->parent.dsize);
    if (new_node->data == NULL)
    {
        vlib_free(new_node);
        return 0;
    }

    new_node->index = index;
    if (data != NULL) memcpy(new_node->data, data, set->parent.dsize);

    set_insert_node(set, new_node);

    set->parent.size++;

    return 1;
}

/** set_erase_fixup
 *  \brief maintaining the properties of red-black tree after erase node
 *  \param[in] set: set handler
 *  \param[in] x: node that needs erase
 *  \return none
 */
static void set_erase_fixup(set_t set, node_t x) 
{
    node_t w = NULL;

    while ((x != set->parent.base) && (x->color == SET_COLOR_BLACK))
    {
        /* this if is mirrored with the corresponding else */
        if (x == x->parent->left)
        {
            /* find the sibling node */
            w = x->parent->right;
            
            /* 1. sibling node is red */
            if (w->color == SET_COLOR_RED)
            {
                w->color = SET_COLOR_BLACK;
                x->parent->color = SET_COLOR_RED;
                
                /* parent node left rotate */
                set_left_rotate(set, x->parent);
                
                w = x->parent->right;
            }
            
            /* 2. sibling node is black, and siling's childs are black */
            if ((w->left->color == SET_COLOR_BLACK) && (w->right->color == SET_COLOR_BLACK))
            {
                w->color = SET_COLOR_RED;
                x = x->parent;
            }
            else
            {
                /* 3. sibling node is black, left child is red and right child is black */
                if (w->right->color == SET_COLOR_BLACK)
                {
                    w->left->color = SET_COLOR_BLACK;
                    w->color = SET_COLOR_RED;
                    
                    /* sibling node right rotate */
                    set_right_rotate(set, w);

                    w = x->parent->right;
                }
                
                /* 4. siling node is black, and siling childs are red */
                w->color = x->parent->color;
                x->parent->color = SET_COLOR_BLACK;
                w->right->color = SET_COLOR_BLACK;
                
                /* parent node left rotate */
                set_left_rotate(set, x->parent);
                
                x = set->parent.base;
            }

        }
        else
        {
            w = x->parent->left;
            if (w->color == SET_COLOR_RED)
            {
                w->color = SET_COLOR_BLACK;
                x->parent->color = SET_COLOR_RED;

                set_right_rotate(set, x->parent);

                w = x->parent->left;
            }

            if ((w->left->color == SET_COLOR_BLACK) && (w->right->color == SET_COLOR_BLACK))
            {
                w->color = SET_COLOR_RED;
                x = x->parent;
            }
            else
            {
                if (w->left->color == SET_COLOR_BLACK)
                {
                    w->right->color = SET_COLOR_BLACK;
                    w->color = SET_COLOR_RED;

                    set_left_rotate(set, w);

                    w = x->parent->left;
                }

                w->color = x->parent->color;
                x->parent->color = SET_COLOR_BLACK;
                w->left->color = SET_COLOR_BLACK;

                set_right_rotate(set, x->parent);

                x = set->parent.base;
            }
        }
    }
    
    x->color = SET_COLOR_BLACK;
}

/** set_mini
 *  \brief find the minimum node in the right subtree
 *  \param[in] set: set handler
 *  \param[in] x: base node
 *  \return minimum node handler
 */
static node_t set_mini(set_t set, node_t x)
{
    if (x == set->nil) return x;
    while (x->left != set->nil)
    {
        x = x->left;
    }

    return x;
}

/** set_maxi
 *  \brief find the maximum node in the right subtree
 *  \param[in] set: set handler
 *  \param[in] x: base node
 *  \return minimum node handler
 */
static node_t set_maxi(set_t set, node_t x)
{
    if (x == set->nil) return x;
    while (x->right != set->nil)
    {
        x = x->right;
    }

    return x;
}

/** set_successor
 *  \brief get the succeed node
 *  \param[in] set: set handler
 *  \param[in] x: base node
 *  \return succeed node handler
 */
static node_t set_successor(set_t set, node_t x) 
{
    node_t y = x->parent;
    
    if (x->right != set->nil)
    {
        return set_mini(set, x->right);
    }

    while ((y != set->nil) && (x == y->right))
    {
        x = y;
        y = y->parent;
    }

    return y;
}

/** value_swap
 *  \brief swap two value
 *  \param[in] *value0: address of value0's pointer
 *  \param[in] *value1: address of value1's pointer
 *  \return none
 */
static void value_swap(void **value0, void **value1)
{
    void *temp;

    temp = *value0;
    *value0 = *value1;
    *value1 = temp;
}

/** set_erase_node
 *  \brief erase node from set
 *  \param[in] set: set handler
 *  \param[in] z: base node
 *  \return node to be released
 */
static node_t set_erase_node(set_t set, node_t z) 
{
    node_t y = set->nil;
    node_t x = set->nil;

    /* the child node has no children or only one child. it directly points to this node */
    if ((z->left == set->nil) || (z->right == set->nil))
    {
        y = z;
    }
    else
    {
        y = set_successor(set, z);
    }

    /* if the son node has an only child, the only child directly inherits its parent's position */
    if (y->left != set->nil)
    {
        x = y->left;
    }
    else if (y->right != set->nil)
    {
        x = y->right;
    }

    x->parent = y->parent;
    if (y->parent == set->nil)
    {
        set->parent.base = x;
    }
    else if (y == y->parent->left)
    {
        y->parent->left = x;
    }
    else
    {
        y->parent->right = x;
    }
    
    /* if y is the smallest node of the right subtree, place y at z, and then delete the original z */
    if (y != z)
    {
        z->index = y->index;
        value_swap(&z->data, &y->data);
    }

    /* if the deleted node is black, maintain the property of set */
    if (y->color == SET_COLOR_BLACK)
    {
        set_erase_fixup(set, x);
    }

    return y;
}

int set_erase(set_t set, int index)
{
    node_t node = NULL;
    node_t cur = NULL;

    if (!set) return 0;

    node = set_find_node(set, index);
    if (node == set->nil)
    {
        return 0;
    }

    cur = set_erase_node(set, node);
    vlib_free(cur->data);
    vlib_free(cur);

    set->parent.size--;

    return 1;
}

void set_clear(set_t set)
{
    if (!set) return;

    recursion_delete_node(set, set->parent.base);
    set->parent.base = set->nil;
    set->parent.size = 0;
}

int set_size(set_t set)
{
    if (!set) return 0;
    return set->parent.size;
}

int set_find(set_t set, int index)
{
    if (!set) return 0;
    return set_find_node(set, index)==set->nil?0:1;
}

void* set_data(set_t set, int index)
{
    if (!set) return NULL;
    return set_find_node(set, index)->data;
}

/** recursion_traverse
 *  \brief recursively traverse data in set
 *  \param[in] set: set handler
 *  \param[in] node: node to be traversed
 *  \param[in] traverse: traverse function
 *  \return none
 */
static void recursion_traverse(set_t set, node_t node, set_traverse_t traverse)
{
    if (node == set->nil)
    {
        return;
    }

    recursion_traverse(set, node->left, traverse);
    traverse(node->index, node->data);
    recursion_traverse(set, node->right, traverse);
}

void set_swap(set_t set, set_t swap)
{
    SET temp;

    if (!set) return;
    if (!swap) return;

    temp = *set;
    *set = *swap;
    *swap = temp;
}

void set_traverse(set_t set, set_traverse_t traverse)
{
    if (!set) return;
    if (!traverse) return;
    recursion_traverse(set, set->parent.base, traverse);
}

void* set_error(set_t set)
{
    if (!set) return NULL;
    return ((node_t)(set->nil))->data;
}

/** set_node_next
 *  \brief set next node
 *  \param[in] set: set handler
 *  \param[in] cur: current node
 *  \return next node
 */
static node_t set_node_next(set_t set, node_t cur)
{
    if (cur->right != set->nil)
    {
        cur = cur->right;
        cur = set_mini(set, cur);
    }
    else  
    {
        if (cur == cur->parent->left) /* current node is left child */
        {
            cur = cur->parent;
        }
        else /* current node is right child */
        {
            cur = cur->parent->parent;
        }
    }

    return cur;
}

/** set_node_prev
 *  \brief set previous node
 *  \param[in] set: set handler
 *  \param[in] cur: current node
 *  \return previous node
 */
static node_t set_node_prev(set_t set, node_t cur)
{
    if (cur->left != set->nil)
    {
        cur = cur->left;
        cur = set_maxi(set, cur);
    }
    else  
    {
        if (cur == cur->parent->right) /* current node is right child */
        {
            cur = cur->parent;
        }
        else /* current node is left child */
        {
            cur = cur->parent->parent;
        }
    }

    return cur;
}

void* set_iterator_begin(vobject_t object)
{
    node_t node = NULL;
    if (!object) return NULL;
    node = set_mini((set_t)object, ((set_t)object)->parent.base);
    return (void *)node;
}

void* set_iterator_end(vobject_t object)
{
    node_t node = NULL;
    if (!object) return NULL;
    node = set_maxi((set_t)object, ((set_t)object)->parent.base);
    return (void *)node;
}

void* set_iterator_move(vobject_t object, void *node, int step)
{
    node_t n = node;
    if (step > 0)
    {
        while (step--) n = set_node_next((set_t)object, n);
    }
    else if (step < 0) 
    {
        while (step++) n = set_node_prev((set_t)object, n);
    }
    return (void *)n;
}

void set_iterator_nfs(void *node, void **first, void **second)
{
    if (!node) return;
    if (first) *first = &(((node_t)node)->index);
    if (second) *second = ((node_t)node)->data;
}

void set_algorithm_swap(vobject_t object, void *node0, void *node1)
{
    set_t set = (set_t)object;
    node_t n0 = node0, n1 = node1;
    void *temp;
    temp = n0->data;
    n0->data = n1->data;
    n1->data = temp;
}
